package cn.lishiyuan.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 编辑距离算法
 */
public class EditDistance {

    /**
     * 莱文斯坦距离（Levenshtein distance）
     * @param word1
     * @param word2
     * @return
     */
    public static int levenshtein(String word1, String word2) {
        char[] source = word1.toCharArray();
        char[] target = word2.toCharArray();
        // 每次对比一个字符
        int[][] dp = new int[source.length][target.length];

        // 初始化第一行 第一行只能从前一个位置转移过来
        for (int j = 0; j < target.length; j++) {
            if (source[0] == target[j]) {
                dp[0][j]= j;
            }else {
                // 不相等则增加一个编辑
                dp[0][j] = j==0 ? 1 : (dp[0][j-1]+1);
            }
        }

        // 初始化第一列 第一列只能从前一个位置转移过来
        for (int i = 0; i < source.length; i++) {
            if (source[i] == target[0]) {
                dp[i][0]= i;
            }else {
                // 不相等则增加一个编辑
                dp[i][0] =  i==0 ? 1 : (dp[i-1][0]+1);
            }
        }

        // 上个状态只能由 i-1 j, i j-1和i-1 j-1转移过来则取他们
        for (int i = 1; i < source.length; i++) {
            for (int j = 1; j < target.length; j++) {
                if (source[i] == target[j]) {
                    // 直接等于替换一个字的情况
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    // 对于每一个字符都有三种选择，删除、增加和替换
                    int i1 = dp[i - 1][j];
                    int j1 = dp[i][j-1];
                    int i1j1 = dp[i-1][j-1];
                    // 取最小的
                    int min = Math.min(i1 + 1, j1 + 1);
                    dp[i][j] = Math.min(min,i1j1+1);
                }
            }
        }

        return dp[source.length-1][target.length-1];
    }

    /**
     * 回溯法
     * @param source
     * @param target
     * @param i
     * @param j
     * @return
     */
    private static int levenshtein(char[] source, char[] target , int i,int j) {
        if(i == source.length || j == target.length){
             // 一个已经到末尾了，另一个还没有，那么他们的长度距离就是剩下距离
            if(i<source.length){
                return source.length - i;
            }
            if (j<target.length){
                return target.length - j;
            }
            return Math.abs(source.length-target.length);
        }

        if (source[i] == target[j]) {
             return levenshtein(source, target, i + 1, j + 1);
        }else {
            // 三种选择
            // 删除一个字符
            int del = levenshtein(source,target,i+1,j);
            // 增加一个字符
            int add = levenshtein(source,target,i,j+1);

            int min = Math.min(del,add);

            // 修改一个字符
            int edit = levenshtein(source, target, i + 1, j + 1);

            return Math.min(edit, min) + 1;
        }
    }


    /**
     * 最长公共子串长度（Longest common substring length）
     * @param word1
     * @param word2
     * @return
     */
    public static int common(String word1, String word2){
        char[] source = word1.toCharArray();
        char[] target = word2.toCharArray();
        // 每次对比一个字符
        int[][] dp = new int[source.length][target.length];

        // 初始化第一行 第一行只能从前一个位置转移过来
        for (int j = 0; j < target.length; j++) {
            if (source[0] == target[j]) {
                // 相等则为1
                dp[0][j] = 1;
            }else {
                if(j==0){
                    dp[0][j] = 0;
                }else {
                    dp[0][j] = dp[0][j-1];
                }
            }
        }

        // 初始化第一列 第一列只能从前一个位置转移过来
        for (int i = 0; i < source.length; i++) {
            if (source[i] == target[0]) {
                // 相等则为1
                dp[i][0] = 1;
            }else {
                if(i==0){
                    dp[i][0] = 0;
                }else {
                    dp[i][0] = dp[i-1][0];
                }
            }
        }

        // 上个状态只能由 i-1 j, i j-1和i-1 j-1转移过来则取他们
        for (int i = 1; i < source.length; i++) {
            for (int j = 1; j < target.length; j++) {
                if (source[i] == target[j]) {
                    // 上个匹配情况下加一
                    int i1j1 = dp[i-1][j-1] + 1;
                    dp[i][j] = i1j1;
                }else {
                    // 当前状态只能从以下三个状态转移而来
                    int i1 = dp[i - 1][j];
                    int j1 = dp[i][j-1];
                    int i1j1 = dp[i-1][j-1];
                    // 取最小的
                    int max = Math.max(i1, j1);
                    dp[i][j] = Math.max(max,i1j1);
                }
            }
        }

        return dp[source.length-1][target.length-1];
    }

}
